/**
 * 1208. 尽可能使字符串相等
 * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/
 */
public class Solutions_1208 {
    public static void main(String[] args) {
//        String s = "abcd", t = "bcdf";
//        int cost = 3;  // output: 3

//        String s = "abcd", t = "cdef";
//        int cost = 3;  // output: 1

//        String s = "abcd", t = "acde";
//        int cost = 0;  // output: 1

        String s = "bbcd", t = "acde";
        int cost = 0;  // output: 0

        int result = equalSubstring(s, t, cost);
        System.out.println(result);
    }

    /**
     * 将字符串转换成 int 数组，则问题转变为：在数组 {1, 1, 1, 1} 中找到和为 3 的最长连续子数组
     */
    public static int equalSubstring(String s, String t, int maxCost) {
        int len = s.length();
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int[] values = new int[len];
        for (int i = 0; i < len; i++) {
            values[i] = Math.abs(sarr[i] - tarr[i]);
        }
        int left = 0, right = 0, max = 0, sum = 0;
        while (right < len) {
            sum += values[right];
            if (sum <= maxCost) {
                // 比较最大的窗口长度
                max = Math.max(max, right - left + 1);
            } else {
                // 收缩窗口：左指针右移
                sum -= values[left];
                left ++;
            }
            right ++;
        }
        return max;
    }
}
